Search for: All records

In their classical paper, Erdős, Goodman and Pósa studied the representation of a graph with vertex set $[n]$ by a family of subsets $$S_1,\dots, S_n$$ with the property that $$\{i,j\}$$ is an edge if and only if $$S_i\cap S_j\neq \emptyset$$. In this note, we consider a similar representation of bounded degree $$r$$-uniform hypergraphs and establish some bounds for a corresponding problem. 

Abstract For any integer$$h\geqslant 2$$ $h⩾2$, a set of integers$$B=\{b_i\}_{i\in I}$$ $B={\left\{b_i\right\}}_{i\in I}$is a$$B_h$$ $B_h$-set if allh-sums$$b_{i_1}+\ldots +b_{i_h}$$ $b_{i_1}+\dots +b_{i_h}$with$$i_1<\ldots $i_1<\dots <i_h$are distinct. Answering a question of Alon and Erdős [2], for every$$h\geqslant 2$$ $h⩾2$we construct a set of integersXwhich is not a union of finitely many$$B_h$$ $B_h$-sets, yet any finite subset$$Y\subseteq X$$ $Y\subseteq X$contains an$$B_h$$ $B_h$-setZwith$$|Z|\geqslant \varepsilon |Y|$$ $\left|Z\right|⩾\epsilon \left|Y\right|$, where$$\varepsilon :=\varepsilon (h)$$ $\epsilon :=\epsilon \left(h\right)$. We also discuss questions related to a problem of Pisier about the existence of a setAwith similar properties when replacing$$B_h$$ $B_h$-sets by the requirement that all finite sums$$\sum _{j\in J}b_j$$ ${\sum }_{j\in J}{b}_j$are distinct. 

Abstract Theregularity methodwas pioneered by Szemerédi for graphs and is an important tool in extremal combinatorics. Over the last two decades, several extensions to hypergraphs were developed which were based on seemingly different notions ofquasirandomhypergraphs. We consider the regularity lemmata for three‐uniform hypergraphs of Frankl and Rödl and of Gowers, and present a new proof that the concepts behind these approaches are equivalent. 

In this paper we make a partial progress on the following conjecture: for every $$\mu>0$$ and large enough $$n$$, every Steiner triple system $$S$$ on at least $$(1+\mu)n$$ vertices contains every hypertree $$T$$ on $$n$$ vertices. We prove that the conjecture holds if $$T$$ is a perfect $$d$$-ary hypertree. 

Abstract A well‐known result of Ajtai Komlós, Pintz, Spencer, and Szemerédi (J. Combin. Theory Ser. A32(1982), 321–335) states that every ‐graph on vertices, with girth at least five, and average degree contains an independent set of size for some . In this paper we show that an independent set of the same size can be found under weaker conditions allowing certain cycles of length 2, 3, and 4. Our work is motivated by a problem of Lo and Zhao, who asked for , how large of an independent set a ‐graph on vertices necessarily has when its maximum ‐degree . (The corresponding problem with respect to ‐degrees was solved by Kostochka, Mubayi, and Verstraëte (Random Struct. & Algorithms44(2014), 224–239).) In this paper we show that every ‐graph on vertices with contains an independent set of size , and under additional conditions, an independent set of size . The former assertion gives a new upper bound for the ‐degree Turán density of complete ‐graphs.